The present invention relates generally to data processing environments and, more particularly, to systems for accessing shared information and other resources, such as in a multi-user database system.
Computers are a powerful tool for the acquisition and processing of information. Computerized databases, which can be regarded as a kind of electronic filing cabinet or repository for collecting computerized data files, are particularly adept at processing vast amounts of information. As such, these systems serve to maintain information in database files or tables and make that information available on demand.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C., An Introduction to Database Systems, Addison-Wesley, 1990; the disclosure of which is hereby incorporated by reference.
Of particular interest to the present invention are those information processing systems which are operative in a shared fashion, i.e., by multiple users (or multiple processes) at a given time. A multi-user database implemented on a client/server platform is one such system. Typically, information sharing or connectivity between the users is provided by a computer network, which comprises several computers connected together as a group. At least one of the computers functions as a "server," providing network services to "clients" (other computers) connected to the network. In this manner, valuable information and resources, including programs, information tables, memory, disk space, printers, and the like, may be shared by several users.
In a multi-user environment, availability of current information to each user is an important consideration. To achieve this, these systems store data objects to be shared (e.g., records of a database file) at a single (logical) location, typically resident on the server. Each user receives access to this centrally-stored information by commanding processes which issue requests to the server for retrieving information of interest. Once received at the client computer, this information may be modified by the client's user and then posted back to the server.
Of course the touchstone of a multi-user environment is sharing; the same holds true for multi-threaded and multi-processing environments. No one user or process can be given access to a given object for long periods of time to the exclusion of others. This is particularly true in a multi-threaded application or in a system which employs multiple processes which have to share certain data structures.
The effectiveness of multi-threaded systems depends in large part on the correct management of concurrency. Data structures, if they are to be shared, should not be accessed in incompatible modes concurrently. Specifically, when one process is accessing a particular data structure, another thread or process should not be updating that data structure at the same time. Even though concurrent "read" access may be granted to multiple processes/threads, efficient implementation results by allowing just one process/thread access to the shared data structure at a time. This way one can avoid building and maintaining queues of different access requests in various access modes. Besides, an access to a shared data structure is typically a quick operation under system control. Therefore, some type of control is required so that they can mutually exclude each other when one of them is executing some program code which is accessing that shared data structure.
The situation is somewhat analogous to "locking." In such an environment, multiple threads or processes may have shared locks, for concurrent "read" access to a particular resource. Unlike conventional locking techniques, however, concurrent access among multiple threads does not employ locking techniques for a particular resource or data structure for reasons of efficiency mentioned above. Instead, the system only permits access by one process or thread at a given time. In such an instance, other processes or threads requiring access to the data structure are put into a "sleep" or "wait" state (i.e., placed in a suspended state until the underlying operating or the database management system is ready to grant access to the desired data structure). The end result is that two concurrent activities do not access shared data at the same time.
Typically, operating systems provide primitives, such as "semaphores" and "mutexes" (mutual exclusive), which gives one thread or one process the right to acquire access to the shared data structure, so that it can proceed with processing of that data structure in an exclusive mode. At the conclusion of processing, that one thread or one process releases the mutex or semaphore, thus relinquishing its exclusive access to the data structure. After that point, another thread or process (typically, one which has been waiting for access to the shared data structure) is granted access and may proceed with its processing of the shared data structure, in an exclusive-access fashion.
Mutexes, which may be built on top of semaphores, are a well-known mechanism for controlling access to shared data structures among concurrent processes or threads. They have a pronounced disadvantage, however. Suppose that one process has to acquire a mutex (i.e., access rights to a shared data object or resource) at different locations (e.g., different routines) of program code. In a scenario, different routines of a computer program may need access to a particular shared data structure at various times. An executing program may, for instance, desire to acquire a mutex in routine A as well as in routine B. Although execution of the program may be such that routine A is called (i.e., invoked) directly or routine B is called directly, it is also possible for routine A to call routine B. Conventional mutex facilities fail at that time, as a result of "deadlock." In particular, when the process or thread is executing in routine A, it acquired the mutex; when the thread or process attempts to acquire the mutex in routine B (i.e., while the mutex is still held through routine A), the thread or process will deadlock on itself (i.e., when attempting to acquire the mutex while executing in routine B). In general, routine A may be called recursively (e.g., A.fwdarw.C.fwdarw.D.fwdarw.A) presenting the same problem.